package ds.hash;

/** 使用再哈希法生成探测序列的开放地址法 */
public class MyHash {

	private DataItem[] dataItemArray;
	private int length;
	private int count;
	private double loadfactor;

	public MyHash() {
		this(11); // 使用质数，在取mod的时候有利于分散聚集
	}
	
	public MyHash(int length){
		this(length, 0.6667);
	}
	
	public MyHash(int length, double loadfactor){
		this.length = length;
		this.loadfactor = loadfactor;
		dataItemArray = new DataItem[length];
	}
	
	public void insert(String key, Object value)
	{
		int index = getHashValue(key);
		int stepSize = getStepSize(key);
		while(dataItemArray[index]!=null && !dataItemArray[index].getKey().equals(key))
		{
			//index++;
			index += stepSize;
			if(index >= length)
				index %= length;
		}
		dataItemArray[index] = new DataItem(key, value);
		count++;
		checkSize();
		return;
	}
	
	public Object get(String key)
	{
		int index = getHashValue(key);
		int stepSize = getStepSize(key);
		while(dataItemArray[index]!=null && !dataItemArray[index].getKey().equals(key))
		{
			//index++;
			index += stepSize;
			if(index == length)
				index %= length;
		}
		if(dataItemArray[index] == null) {
			return null;
		}
		else {
			if(dataItemArray[index].isDeleted())
				return null;
			else
				return dataItemArray[index].getValue();
		}
	}
	
	public Object delete(String key)
	{
		int index = getHashValue(key);
		int stepSize = getStepSize(key);
		while(dataItemArray[index]!=null && !dataItemArray[index].getKey().equals(key))
		{
			//index++;
			index += stepSize;
			if(index == length)
				index %= length;
		}
		if(dataItemArray[index] == null) {
			return null;
		}
		else {
			if(dataItemArray[index].isDeleted())
				return null;
			else
				dataItemArray[index].setDeleted(true);
				count--;
				return dataItemArray[index].getValue();
		}
	}

	/** 得到哈希值，自己定义的 */
	private int getHashValue(String key)
	{
		key = key.toLowerCase();
		int hashValue = 0;
		for(int i=0;i<key.length();i++)
		{
			int number = key.charAt(i) - 96;
			hashValue = (hashValue * 27 + number) % length;
		}
		return hashValue >=0? hashValue : -hashValue;
		
		/*
		int value = Math.abs(key.hashCode());
		return value % length;
		*/
	}
	
	private int getStepSize(String key)
	{
		return 5 - Math.abs(key.hashCode()) % 5;
	}
	
	private void checkSize()
	{
		if((count + .0)/ (length + .0) > loadfactor)
			increase();
	}

	/** 扩容 */
	private void increase()
	{
		DataItem[] formerArray = dataItemArray;
		length = getPrimeNumberNotLessThan(length*2);
		dataItemArray = new DataItem[length];
		count = 0;
		for(int i=0;i<formerArray.length;i++)
		{
			if(formerArray[i]!=null && !formerArray[i].isDeleted())
			{
				Object value = formerArray[i].getValue();
				String key = formerArray[i].getKey();
				insert(key, value);
			}
		}
	}
	
	/** 得到不小于某个数的质数 */
	private int getPrimeNumberNotLessThan(int value)
	{
		while(true)
		{
			int upperLimit = (int)Math.sqrt(value);
			int i;
			for(i=2;i<=upperLimit && value % i != 0;i++);
			if(i>upperLimit)
				return value;
			else
				value++;
		}
	}
}

class DataItem{
	private String key;
	private Object value;
	private boolean deleted;
	
	public DataItem(String key, Object value)
	{
		this.key = key;
		this.value = value;
	}
	
	public String getKey() {
		return key;
	}
	public Object getValue() {
		return value;
	}

	public boolean isDeleted() {
		return deleted;
	}

	public void setDeleted(boolean deleted) {
		this.deleted = deleted;
	}
}

class Point
{
	int x;
	int y;
	
	public Point(int x, int y)
	{
		this.x = x;
		this.y = y;
	}
	
	public String toString() {
		return this.x + " " + this.y;
	}
}
class MyHashApp {
	public static void main(String[] args) {

		/*MyHash mh = new MyHash();
		Point p1 = new Point(1,2);
		Point p2 = new Point(3,4);
		Point p3 = new Point(5,6);
		Point p4 = new Point(7,8);
		Point p5 = new Point(9,10);
		Point p6 = new Point(9,10);
		Point p7 = new Point(9,10);
		mh.insert("p1", p1);
		mh.insert("p2", p2);
		mh.insert("p3", p3);
		mh.insert("p4", p4);
		mh.insert("p5", p5);
		mh.insert("p6", p6);
		mh.insert("p7", p7);
		mh.insert("p8", p7);
		
		System.out.println(mh.get("p1"));
		System.out.println(mh.get("p1").equals(p1));
		
		System.out.println((int)7.8);*/
		System.out.println((char)97);
	}
}